模式识别与人工智能
Friday, Apr. 4, 2025 Home      About Journal      Editorial Board      Instructions      Ethics Statement      Contact Us                   中文
  2016, Vol. 29 Issue (5): 400-409    DOI: 10.16451/j.cnki.issn1003-6059.201605003
Papers and Reports Current Issue| Next Issue| Archive| Adv Search |
Graph-Based Algorithm for Pattern Matching with Bounded Length Gaps and One-off Constraint
HU Xuegang, WANG Haiping, GUO Dan, LI Peipei
School of Computer Science and Information, Hefei University of Technology, Hefei 230009

Download: PDF (514 KB)   HTML (1 KB) 
Export: BibTeX | EndNote (RIS)      
Abstract  The problem of pattern matching with bounded length gaps and one-off constraint (PMGO) is discussed. The structure of individual occurrences is changed by the bounded gaps, and the relation between occurrences is restricted by the one-off constraint. Thus, a large-scale sparse space of all candidate occurrences is generated. Based on the framework of the constraint satisfaction, the PMGO problem is transformed into path search in a directed acyclic graph (DAG) structure. Meanwhile, the equivalence of transformation is proved. Then, a graph-based pruning and matching (GPM) algorithm is presented. In GPM algorithm, a constraint relationship between vertexes is built under the one-off constraint, and then the path search is combined with a pruning procedure in an alternating and iterative manner. The loss rate of occurrences is used to measure existing heuristic algorithms and the completeness of the proposed GPM algorithm. The experimental results demonstrate that the GPM algorithm provides a complementary method for heuristic algorithms and it efficiently reduces the loss rate of occurrences.
Received: 03 April 2015     
About author:: 胡学钢,男,1961年生,博士,教授,主要研究方向为数据挖掘、知识工程.Email:jsjxhuxg@hfut.edu.cn.  王海平,男,1986年生,博士研究生,主要研究方向为模式识别、数据挖掘.Email:hpwang.hfut@gmail.com. 郭丹,女,1983年生,博士,副教授,主要研究方向为模式识别、智能地理信息系统.Email:guodan@hfut.edu.cn.李培培(通讯作者),女,1982年生,博士,讲师,主要研究方向为概念漂移检测、数据流分类.Email:peipeili@hfut.edu.cn.
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:   
URL:  
http://manu46.magtech.com.cn/Jweb_prai/EN/10.16451/j.cnki.issn1003-6059.201605003      OR     http://manu46.magtech.com.cn/Jweb_prai/EN/Y2016/V29/I5/400
Copyright © 2010 Editorial Office of Pattern Recognition and Artificial Intelligence
Address: No.350 Shushanhu Road, Hefei, Anhui Province, P.R. China Tel: 0551-65591176 Fax:0551-65591176 Email: bjb@iim.ac.cn
Supported by Beijing Magtech  Email:support@magtech.com.cn